package com.java.container;

import java.util.Comparator;
import java.util.HashMap;

/**
 * @program: java_basic_knowledge
 * @description:
 * @author: CaoYong
 * @create: 2021-04-16 16:02
 **/
public class TreeMapKnowlege {

    public static class HowToDefineTreeMap<K, V> {

        private final Comparator<? super K> comparator;
        private Entry<K,V> root = null;
        int size = 0;
        int modCount;


        public HowToDefineTreeMap(Comparator<? super K> comparator) {
            this.comparator = comparator;
        }

        public V put(K key, V value) {

            Entry<K, V> t = root;
            // 当添加第一个节点的时候，root为null，新建一个节点并设置root指向它，size设置为1
            if(t == null) {
                compare(key, key);
                root = new Entry<>(key, value, null);
                size = 1;
                modCount ++;
                return null;
            }

            // 当root不空时，从根节点开始循环,t指向当前比较节点，parent为t的父节点，循环结束后parent就是要找的父节点
            // t开始指向根节点，从根节点开始比较，如果小于根节点就将t设置为左孩子,与左孩子比较，大于就和右孩子比较，一直比到null或比较结果为0，为0则设置值
            // t为null，则当退出循环时，parent就指向待插入节点的父节点
            int cmp;
            Entry<K, V> parent;
            Comparator<? super K> cpr = comparator;
            // comparator不为null时
            if (cpr != null) {
                do {
                    parent = t;
                    cmp = cpr.compare(key, t.key);
                    if (cmp < 0) {
                        t = t.left;
                    }
                    else if (cmp > 0) {
                        t = t.right;
                    }
                    else {
                        return t.setValue(value);
                    }
                } while (t != null);
            }
            // comparator为null时
            else{
                if(key == null) {
                    throw new NullPointerException();
                }
                Comparable<? super K> k = (Comparable<? super K>) key; //如果没有设置comparator，则假设key一定实现了Comparable接口，使用Comparable接口的CompareTo
                do {
                    parent = t;
                    cmp = k.compareTo(t.key);
                    if (cmp < 0) {
                        t = t.left;
                    }
                    else if(cmp > 0) {
                        t = t.right;
                    }
                    else {
                        return t.setValue(value);
                    }
                } while (t != null);

                }

            // 找到父节点后，就新加一个节点，根据新的键与父节点键的比较结果，判断插入为左孩子还是右孩子
            Entry<K, V> e = new Entry<>(key, value, parent);
            if (cmp < 0) {
                parent.left = e;
            }
            else {
                parent.right = e;
            }
//            fixAfterInsertion(e); 用于调整数的结构使其符合红黑树的约束
            size ++;
            modCount ++;
            return e.getValue();

        }

        public V get(Object key) {
            Entry<K, V> p = getEntry(key);
            return (p == null ? null : p.value);
        }

        private Entry<K,V> getEntry(Object key) {
            if (comparator != null) {
//                return getEntryUsingComparator(key); // 如果comparator不为空，则调用单独的方法getEntryUsingComparator
                return null;
            }
            if (key == null) {
                throw new NullPointerException();
            }
            Comparable<? super K> k = (Comparable<? super K>) key;
            Entry<K, V> p = root;
            while (p != null) {
                int cmp = k.compareTo(p.key);
                if(cmp < 0) {
                    p = p.left;
                }
                else if (cmp > 0) {
                    p = p.right;
                }
                else {
                    return p;
                }
            }
            return null;
        }

        public V remove(Object key) {
            Entry<K, V> p = getEntry(key);
            if (p == null) {
                return null;
            }
            V oldValue = p.value;
//            deleteEntry(p);
            return oldValue;
        }

        private int compare(Object k1, Object k2) {
            return comparator == null ? ((Comparable<? super  K>) k1).compareTo((K) k2) : comparator.compare((K)k1, (K)k2);
        }

        /**
         * 键值对类
         * @param <K>
         * @param <V>
         */
        public class Entry<K, V> {
            final boolean BLACK = false;
            K key;
            V value;
            Entry<K, V> left = null; //左节点
            Entry<K, V> right = null; //右节点
            Entry<K, V> parent; //父节点
            boolean color = BLACK; //节点的颜色，非红即黑，用boolean表示

            public Entry(K key, V value, Entry<K, V> parent) {
                this.key = key;
                this.value = value;
                this.parent = parent;
            }

            public void setKey(K key) {
                this.key = key;
            }

            public V setValue(V value) {
                this.value = value;
                return value;
            }

            public V getValue() {
                return value;
            }
        }
    }
}
